//https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/?envType=daily-question&envId=2024-01-26


class Solution {
public:
    static const int N = 10010;
    using pii = pair<int, int>;
    vector<pii>g[N];
    int depth[N];
    int cnt[N][15][30];
    int pa[N][30];
    void dfs(int x, int fa){
        pa[x][0] = fa;
        for(auto c : g[x]){
            if(c.first != fa){
                cnt[c.first][0][c.second] = 1;
                depth[c.first] = depth[x] + 1;
                dfs(c.first, x);
            }
        }
    }
    vector<int> minOperationsQueries(int n, vector<vector<int>> &edges, vector<vector<int>> &queries) {
        for(auto x : edges){
            int a = x[0], b = x[1], c = x[2];
            g[a].push_back({b, c});
            g[b].push_back({a, c});
        }
        memset(pa, -1, sizeof pa);
        dfs(0, -1);
        for(int j = 1; j < 15; j++){
            for(int i = 0; i < n; i++){
                if(pa[i][j - 1] != -1){
                    pa[i][j] = pa[pa[i][j - 1]][j - 1];
                    for(int k = 0; k <= 26; k++){
                        cnt[i][j][k]  = cnt[i][j - 1][k] + cnt[pa[i][j - 1]][j - 1][k];
                    }
                }
            }
        }
        
        vector<int>res;
        for(auto x : queries){
            int a = x[0], b = x[1];
            if(a == b){
                res.push_back(0);
                continue;
            }
            int totaldeep = depth[a] + depth[b];
            if(depth[a] > depth[b])swap(a, b);
            int dif = depth[b] - depth[a];
            int curcnt[30] = {0};
                
            for(int j = 0; j < 15; j++){
                if((dif >> j) & 1){
                    for(int k = 0; k <= 26; k++){
                        curcnt[k] += cnt[b][j][k];
                    }
                    b = pa[b][j];
                }
            }
            if(a != b ){
                for(int i = 15; i >= 0; i--){
                    if(a == -1 || b == -1)continue;
                    int la = pa[a][i], lb = pa[b][i];
                    if(la == -1)continue;
                    if(la != lb){
                        for(int j = 0; j <= 26; j++){
                            curcnt[j] += cnt[a][i][j] + cnt[b][i][j];
                        }
                        a = la;
                        b = lb;
                    }
                }
                for(int i = 0; i <= 26; i++){
                    curcnt[i] += cnt[a][0][i] + cnt[b][0][i];
                }
            } 
            int lca = (a == b) ? a : pa[a][0];

            int diff = totaldeep - 2 * depth[lca];
            
            int mac = 0;
           
            for(int i = 0; i <= 26; i++){
                mac = max(mac, curcnt[i]);
            }
            res.push_back(diff - mac);
        }
        return res;
    }
};